package com.c2b.algorithm.leetcode.base;

import java.util.*;

/**
 * <a href="https://leetcode.cn/problems/combination-sum/">组合总和(Combination Sum)</a>
 * <p>给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。</p>
 * <p>candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。 </p>
 * <p>对于给定的输入，保证和为 target 的不同组合数少于 150 个。</p>
 *
 * <p>
 * <b>示例：</b>
 * <pre>
 * 示例 1：
 *      输入：candidates = [2,3,6,7], target = 7
 *      输出：[[2,2,3],[7]]
 *      解释：
 *          2 和 3 可以形成一组候选，2 + 2 + 3 = 7 。注意 2 可以使用多次。
 *          7 也是一个候选， 7 = 7 。
 *          仅有这两种组合。
 *
 * 示例 2：
 *      输入: candidates = [2,3,5], target = 8
 *      输出: [[2,2,2,2],[2,3,3],[3,5]]
 *
 * 示例 3：
 *      输入: candidates = [2], target = 1
 *      输出: []
 * </pre>
 * </p>
 *
 * <p>
 * <b>提示：</b>
 *  <ul>
 *      <li>1 <= candidates.length <= 30</li>
 *      <li>2 <= candidates[i] <= 40</li>
 *      <li>candidates 的所有元素 互不相同</li>
 *      <li>1 <= target <= 40</li>
 *  </ul>
 * </p>
 *
 * @author c2b
 * @see LC0039CombinationSum_M
 * @see LC0040CombinationSum_II_M
 * @see LC0216CombinationSum_III_M
 * @see LC0377CombinationSum_IV_M
 * @since 2024/2/22 16:31
 */
public class LC0039CombinationSum_M {

    static class Solution {
        public List<List<Integer>> combinationSum(int[] candidates, int target) {
            List<List<Integer>> resList = new ArrayList<>();
            Arrays.sort(candidates);
            search(candidates, 0, target, new LinkedList<>(), resList);
            return resList;
        }

        private void search(int[] candidates, int startPoint, int target, Deque<Integer> path, List<List<Integer>> resList) {
            if (target == 0) {
                resList.add(new ArrayList<>(path));
            }
            for (int i = startPoint; i < candidates.length; i++) {
                // 因为数组是有序的，candidates[i] > target时 ，后续无法找出和为target的组合
                if (candidates[i] > target) {
                    return;
                }
                // 1.先尝试选取当前数字
                path.addLast(candidates[i]);
                // 由于每一个元素可以重复使用，下一轮的搜索起点仍然是 i
                search(candidates, i, target - candidates[i], path, resList);
                // 2.未选取当前数字
                path.removeLast();
            }
        }
    }
}
